#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define HASH_MULT  314159     /* random multiplier */
#define HASH_PRIME 516595003  /* the 27182818th prime; it's less than $2^{29}$ */
#define maxV 65535
#define URL_SIZE 1024

static int hash_head[maxV];
static int hash_link[maxV];

char **url_table;
int url_table_size; 
int i;
char http[] = "http://";

/* http:.../~pf/algoritmos_para_grafos/aulas/digraphdatastructs.html */

char *adjust_url (char *url) {
  int j, url_size;

  if (strstr(url, http)) url = url + 7;

  /* Tira a '/' do final da url analisada*/
  url_size = strlen(url);
  for (j = url_size - 1; j >= 0; j--) {
    if (isalnum(url[j])) {
      url[j + 1] = '\0';
      break;
    }
    else if (url[j] == '/') {
      url[j] = '\0';
      break;
    }
  }
  return url;
}

int hash_full ()
{
  return (i >= url_table_size);
}

void hash_setup (int size)
{
  register int v;

  url_table_size = size;
  for (v = 0; v < size; v++) hash_head[v] = -1;
  url_table = malloc(size * sizeof(char *));
  for (v = 0; v < url_table_size; v++) url_table[v] = malloc(URL_SIZE * sizeof(char));
  i = 0;
}

int hash_in (char *url)
{
  register int u;
  register long h;

  url = adjust_url(url);

  if (url) url_table[i] = strcpy(url_table[i], url);
  else {
    printf("HASH ERROR!\n");
    return -1;
  }
  //Find vertex u, whose location is the hash code for string t
  for (h = 0; *url; url++) {
    h += (h ^ (h >> 1)) + HASH_MULT * (unsigned char)*url;
    while (h >= HASH_PRIME) h -= HASH_PRIME;
  }
  u = h % url_table_size;

  hash_link[i] = hash_head[u];
  hash_head[u] = i++;
  return i - 1;
}

int hash_out (char *s)
{
  register char *t;
  register int u;
  register long h;

  s = adjust_url(s);
  t = s;

  // Find vertex u, whose location is the hash code for string t
  for (h = 0; *t; t++) {
    h += (h ^ (h >> 1)) + HASH_MULT * (unsigned char)*t;
    while (h >= HASH_PRIME) h -= HASH_PRIME;
  }
  u = h % url_table_size;

  for (u = hash_head[u]; u != -1; u = hash_link[u]) {
    if (strcmp(s, url_table[u]) == 0) {
      return u;
    }
  }

  return -1;
}

void hash_cleanup ()
{
  int i;
  printf("Cleaning hash table...\n");
  for (i = 0; i < url_table_size; i++) free(url_table[i]);
  free(url_table);
}

